package nachos.threads;

import nachos.machine.*;

import java.util.Comparator;
import java.util.TreeSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Queue;

/**
 * A scheduler that chooses threads based on their priorities.
 *
 * <p>
 * A priority scheduler associates a priority with each thread. The next thread
 * to be dequeued is always a thread with priority no less than any other
 * waiting thread's priority. Like a round-robin scheduler, the thread that is
 * dequeued is, among all the threads of the same (highest) priority, the
 * thread that has been waiting longest.
 *
 * <p>
 * Essentially, a priority scheduler gives access in a round-robin fassion to
 * all the highest-priority threads, and ignores all other threads. This has
 * the potential to
 * starve a thread if there's always a thread waiting with higher priority.
 *
 * <p>
 * A priority scheduler must partially solve the priority inversion problem; in
 * particular, priority must be donated through locks, and through joins.
 */
public class PriorityScheduler extends Scheduler {
    /**
     * Allocate a new priority scheduler.
     */
    public PriorityScheduler() {
    }
    
    /**
     * Allocate a new priority thread queue.
     *
     * @param	transferPriority	<tt>true</tt> if this queue should
     *					transfer priority from waiting threads
     *					to the owning thread.
     * @return	a new priority thread queue.
     */
    public ThreadQueue newThreadQueue(boolean transferPriority) {    	
	return new PriorityQueue(transferPriority);
    }

    public int getPriority(KThread thread) {
	Lib.assertTrue(Machine.interrupt().disabled());
		       
	return getThreadState(thread).getPriority();
    }

    public int getEffectivePriority(KThread thread) {
	Lib.assertTrue(Machine.interrupt().disabled());
		       
	return getThreadState(thread).getEffectivePriority();
    }

    public void setPriority(KThread thread, int priority) {
	Lib.assertTrue(Machine.interrupt().disabled());
		       
	Lib.assertTrue(priority >= getPriorityMinimum() &&
		   priority <= getPriorityMaximum());
	
	getThreadState(thread).setPriority(priority);
    }

    public boolean increasePriority() {
	boolean intStatus = Machine.interrupt().disable();
		       
	KThread thread = KThread.currentThread();

	int priority = getPriority(thread);
	if (priority == getPriorityMaximum())
	    return false;

	setPriority(thread, priority+1);

	Machine.interrupt().restore(intStatus);
	return true;
    }

    public boolean decreasePriority() {
	boolean intStatus = Machine.interrupt().disable();
		       
	KThread thread = KThread.currentThread();

	int priority = getPriority(thread);
	if (priority == priorityMinimum)
	    return false;

	setPriority(thread, priority-1);

	Machine.interrupt().restore(intStatus);
	return true;
    }

    /**
     * The default priority for a new thread. Do not change this value.
     */
    public static final int priorityDefault = 1;
    /**
     * The minimum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMinimum = 0;
    /**
     * The maximum priority that a thread can have. Do not change this value.
     */
    public static final int priorityMaximum = 7;    

    public int getPriorityMaximum(){
    	return priorityMaximum;
    }
    
    public int getPriorityMinimum(){
    	return priorityMinimum;
    }

    public int getPriorityDefault(){
    	return priorityDefault;
    }
    
    /**
     * Return the scheduling state of the specified thread.
     *
     * @param	thread	the thread whose scheduling state to return.
     * @return	the scheduling state of the specified thread.
     */
    protected ThreadState getThreadState(KThread thread) {    	
    	
	if (thread.schedulingState == null)
	    thread.schedulingState = new ThreadState(thread);

	return (ThreadState) thread.schedulingState;
    }

    /**
     * A <tt>ThreadQueue</tt> that sorts threads by priority.
     */
    protected class PriorityQueue extends ThreadQueue {
    	
    PriorityQueue(boolean transferPriority) {
	    this.transferPriority = transferPriority;
	}

	public void waitForAccess(KThread thread) {
	    Lib.assertTrue(Machine.interrupt().disabled());
	    ThreadState waitingThreadState = getThreadState(thread);
	    waitingThreadState.waitForAccess(this);
	    
	    waitQueue.add(getThreadState(thread));
	    if(owner != null){
	    	getThreadState(owner).donatePriority(waitingThreadState.getPriority());
	    }
	}

	public void acquire(KThread thread) {
	    Lib.assertTrue(Machine.interrupt().disabled());
	    getThreadState(thread).acquire(this);
	    
	    this.owner = thread;
	}

	/**
	 * Peter Thai - Implemented
	 * Return the next thread in the queue and acquires waitQueue
	 *
	 * @return	the next thread that <tt>nextThread()</tt> would
	 *		return.
	 */

	public KThread nextThread() {
	    Lib.assertTrue(Machine.interrupt().disabled());

		if(waitQueue.isEmpty())
			return null;
		
		waitQueue.peek().acquire(this); // Next thread acquires the wait queue
		return waitQueue.poll().thread; // Remove & return thread from queue
	}

	/**
	 * Peter Thai - Implemented
	 * Return the next thread that <tt>nextThread()</tt> would return,
	 * without modifying the state of this queue.
	 *
	 * @return	the next thread that <tt>nextThread()</tt> would
	 *		return.
	 */
	protected ThreadState pickNextThread() {
	    Lib.assertTrue(Machine.interrupt().disabled());

	    /* PriorityQueues already return null if queue is empty
		if(waitQueue.isEmpty())
			return null;
		*/
		
		return waitQueue.peek(); // Returns head of queue without removal
	}

	/**
	 * Peter Thai - Implemented
	 * Print out the waitQueue for debugging
	 *
	 */
	
	public void print() {
	    Lib.assertTrue(Machine.interrupt().disabled());
		for(Iterator itr = waitQueue.iterator(); itr.hasNext(); ){
			System.out.println((KThread) itr.next());
		}
	}

	public Integer getMaximumPriority(){
		ThreadState threadState = waitQueue.peek();
		if(threadState != null)
			return threadState.getPriority();
		else
			return null;
	}
	
	/**
	 * <tt>true</tt> if this queue should transfer priority from waiting
	 * threads to the owning thread.
	 */
	public boolean transferPriority;

	
	protected KThread owner;
	private Queue<ThreadState> waitQueue = new java.util.PriorityQueue <ThreadState> (15, new priorityComparator());
	
		public class priorityComparator implements Comparator<ThreadState>{

			public int compare(ThreadState leftThread, ThreadState rightThread){
				int leftPriority = leftThread.getEffectivePriority();
				int rightPriority = rightThread.getEffectivePriority();

				if (leftPriority > rightPriority)
					return 1;
				if(leftPriority < rightPriority)
					return -1;
				return 0;
			}
		}

    } //END Class PriorityQueue

    /**
     * The scheduling state of a thread. This should include the thread's
     * priority, its effective priority, any objects it owns, and the queue
     * it's waiting for, if any.
     *
     * @see	nachos.threads.KThread#schedulingState
     */
    protected class ThreadState {
	/**
	 * Allocate a new <tt>ThreadState</tt> object and associate it with the
	 * specified thread.
	 *
	 * @param	thread	the thread this state belongs to.
	 */
	public ThreadState(KThread thread) {
	    this.thread = thread;
	    setPriority(getPriorityDefault());
	    
	    System.out.println("PRIORITY-SCHED:: New thread: priority = " + getPriority());
	}

	/**
	 * Return the priority of the associated thread.
	 *
	 * @return	the priority of the associated thread.
	 */
	public int getPriority() {
	    return priority;
	}

	/**
	 * Return the effective priority of the associated thread.
	 *
	 * @return	the effective priority of the associated thread.
	 */
	public int getEffectivePriority() {
		int threadWeight = priority+donations;

		if(waitQueue.transferPriority)
				effectivePriority = threadWeight;
		else 
			effectivePriority = priority;
		
	    return effectivePriority;
	}

	/**
	 * Set the priority of the associated thread to the specified value.
	 *
	 * @param	priority	the new priority.
	 */
	public void setPriority(int priority) {
		
		//System.out.println("======> TEST OKAY");
	    if (this.priority == priority)
	    	return;
	    
	    this.priority = priority;
	    this.effectivePriority = -1;
	}

	public void donatePriority(int donation){
		if(donation + this.donations < getPriorityMaximum())
			this.donations += donation;
		else
			this.priority = getPriorityMaximum(); //this.effectivePriority = priorityMaximum;
	}
	
	
	/** 
	 * Peter Thai - Implemented
	 * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
	 * the associated thread) is invoked on the specified priority queue.
	 * The associated thread is therefore waiting for access to the
	 * resource guarded by <tt>waitQueue</tt>. This method is only called
	 * if the associated thread cannot immediately obtain access.
	 *
	 * @param	waitQueue	the queue that the associated thread is
	 *				now waiting on.
	 *
	 * @see	nachos.threads.ThreadQueue#waitForAccess
	 */
	public void waitForAccess(PriorityQueue waitQueue) {
		System.out.println("LOTTERY-SCHEDULER :: in WaitforAccess!!");
		this.waitQueue = waitQueue;
	}

	/**
	 * Called when the associated thread has acquired access to whatever is
	 * guarded by <tt>waitQueue</tt>. This can occur either as a result of
	 * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
	 * <tt>thread</tt> is the associated thread), or as a result of
	 * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
	 *
	 * @see	nachos.threads.ThreadQueue#acquire
	 * @see	nachos.threads.ThreadQueue#nextThread
	 */
	public void acquire(PriorityQueue waitQueue) {
		this.effectivePriority = -1;
		this.donations = 0;
		this.waitQueue = null;
	}	

	/** The thread with which this object is associated. */	   
	protected KThread thread;
	/** The priority of the associated thread. */
	protected int priority;
	protected int effectivePriority;
	protected int donations;
	private PriorityQueue waitQueue;
    } // END class ThreadState
    
    public static void selfTest(){
    	/*
    	Alarm testAlarm = new Alarm();
    	
    	System.out.println();
    	System.out.println("=======================================");
        System.out.println("Testing Priority Scheduler");
        System.out.println("=======================================");
        
        KThread t1 = new KThread(new Runnable(){
                public void run(){
                        Machine.interrupt().disable();
                        KThread.sleep();
                        Machine.interrupt().enable();
                        System.out.println("T1 :: Running!");
                }
        });
        t1.setName("T1");

        KThread t2 = new KThread(new Runnable(){
                public void run(){
                        Machine.interrupt().disable();
                        KThread.sleep();
                        Machine.interrupt().enable();
                        System.out.println("T2 :: Running!");
                }
        });
        t2.setName("T2");
        
        KThread t3 = new KThread(new Runnable(){
                public void run(){
                        Machine.interrupt().disable();
                        KThread.sleep();
                        Machine.interrupt().enable();
                        System.out.println("T3 :: Running!");
                }
        });
        t3.setName("T3");
        
        t1.fork();
        t2.fork();
        t3.fork();

        testAlarm.waitUntil(100000);
        Machine.interrupt().disable();        
        
        ThreadState s1 = (ThreadState)t1.schedulingState;
        ThreadState s2 = (ThreadState)t2.schedulingState;
        ThreadState s3 = (ThreadState)t3.schedulingState;
        
        //s1.setPriority(1);
        //s2.setPriority(4);
        //s3.setPriority(priorityMaximum);

        t1.ready();
        t2.ready();
        t3.ready();
        Machine.interrupt().enable();

        t1.join();
        t2.join();
        t3.join();
        */
    }
    
}
